using Link;

public class LinkedList<T> : IListDS<T>
{
    /// <summary>
    /// 构造个空单链表
    /// </summary>
    public LinkedList()
    {
        Head = null;
    }
    /// <summary>
    /// 头指针
    /// </summary>
    /// <value></value>
    public Node<T> Head { get; set; }

    public void Append(T item)
    {
        throw new NotImplementedException();
    }

    public void Clear() => Head = null;

    /// <summary>
    /// 删除
    /// </summary>
    /// <param name="i"></param>
    /// <returns></returns>
    public T Delete(int i)
    {
        if (IsEmpty() || i < 0)
        {
            System.Console.WriteLine("链表为空或位置错误");
            return default(T);
        }
        Node<T> q = new Node<T>();
        //如果删除头结点，直接把头指针指向头结点指向的元素
        if (i == 1)
        {
            q = Head;
            Head = Head.Next;
            return q.Data;
        }
        Node<T> p = Head;
        int j = 1;
        while (p.Next != null && j < i)
        {
            q = p;
            p = p.Next;
            j++;
        }
        if (j != i)
        {
            System.Console.WriteLine("位置错误");
            return default(T);
        }
        //此时q为待删除节点的前驱节点 p为待删除的节点 q.Next=p
        q.Next = p.Next;
        return p.Data;
    }

    public T GetElem(int i)
    {
        if (IsEmpty())
        {
            System.Console.WriteLine("表空");
            return default(T);
        }
        var p = Head;
        int j = 1;
        while (p.Next != null && j < i)
        {
            p = p.Next;
            j++;
        }
        if (i != j)
        {
            System.Console.WriteLine("位置错误");
            return default(T);
        }
        return p.Data;
    }

    /// <summary>
    /// 求单链表的长度需要遍历整个链表，所以，时间复杂度为O(n)，n 是单链表的长度。 
    /// </summary>
    /// <returns></returns>
    public int GetLength()
    {
        Node<T> p = Head;
        int length = 0;
        while (p != null)
        {
            length++;
            p = p.Next;
        }
        return length;
    }

    /// <summary>
    /// 在任意位置插入节点
    /// </summary>
    /// <param name="item"></param>
    /// <param name="i"></param>
    public void Insert(T item, int i)
    {
        if (i < 1)
        {
            System.Console.WriteLine("位置错误");
            return;
        }
        //插入到头结点之前
        if (i == 1)
        {
            //要插入的节点
            Node<T> q = new Node<T>(item);
            q.Next = Head;
            Head = q;
            return;
        }
        Node<T> p = Head;
        int j = 1;
        //循环完了之后  p为i-1位置的节点
        while (p.Next != null && j < i)
        {
            p = p.Next;
            j++;
        }
        if (j != i)
        {
            System.Console.WriteLine("位置错误");
            return;
        }
        Node<T> node = new Node<T>(item);
        //顺序必须是下面顺序，否则会造成p.Next的值被覆盖
        //把待插入节点的指针指向i
        node.Next = p.Next;
        //把i-1的指针指向待插入节点
        p.Next = node;
    }

    public bool IsEmpty() => Head == null;

    public bool IsFull()
    {
        throw new NotImplementedException();
    }

    public int Locate(T value)
    {
        if (IsEmpty())
        {
            System.Console.WriteLine("表空");
            return -1;
        }
        var p=Head;
        int i=1;
        while (p.Next!=null)
        {
            if(p.Data.Equals(value))
            {
                return i;
            }
            i++;
        }
        return -1;
    }
}